/**
 * 
 */
package combinatorics;

import java.util.ArrayList;

/**
 * @author Michael
 *
 */
public class PrintAllSubsetsOfSizeK {

	// from justin to be studied
	public static void allSubsetsOfSizeKIterative(int[] s, int k) {
		int subsets = 1 << s.length;// number of subsets
		for (int i = 1; i <= subsets; i++) {
			int n = i; // use each bit in n to determine whether to print the
			int ones = 0;
			while (n > 0) {
				if ((n & 1) == 1)
					ones++;
				n >>= 1;
			}
			if (ones == k) {
				n = i;
				// corresponding number in s
				int shift = 0;
				while (shift < s.length) {
					// if the bit is 1, print
					boolean print = ((n >> shift) & 1) == 1;
					if (print)
						System.out.print(s[shift]);
					shift++;
				}
				System.out.println();
			}
		}
	}

	// from justin to be studied
	public static void allSubsetsOfSizeKRecursive(int[] a, int start, int k,
			String s) {
		if (k == 0) {
			System.out.println(s);
		} else
			for (int i = start; i <= a.length - k; i++) {
				allSubsetsOfSizeKRecursive(a, i + 1, k - 1, s + a[i]);
			}
	}

	public static void allSubsetsOfSizeKRecursive(int[] a, int index, int k,
			ArrayList<Integer> l) {
		assert (k <= a.length);
		if (0 == k) {
			for (int i : l) {
				System.out.printf("%d ", i);
			}
			System.out.println();
		} else if (index <= a.length - k) {
			l.add(a[index]);
			allSubsetsOfSizeKRecursive(a, index + 1, k - 1, l);
			l.remove(l.size() - 1);
			allSubsetsOfSizeKRecursive(a, index + 1, k, l);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int k = 3;
		int[] set = new int[] { 1, 2, 3, 4, 5 };
		allSubsetsOfSizeKRecursive(set, 0, k, "");
		// allSubsetsOfSizeKIterative(set, k);
		//allSubsetsOfSizeKRecursive(set, 0, k, new ArrayList<Integer>());
	}

	/**
	 * 
	 */
	public PrintAllSubsetsOfSizeK() {
		// TODO Auto-generated constructor stub
	}
}
